The present invention relates to the art of processing digital images. More particularly, the present invention relates to the art of locating edges of a digital image.
In many visual inspection applications, for example in production control and quality assurance during manufacturing, accurate edge detection and measurements are essential. To detect, or locate, edges of manufactured goods, one or more images are taken of the goods. In computer or machine vision applications, the image taken is typically represented by a two-dimensional (2D) array of pixels, each pixel having one gray value (or three values representing a color). Then, the image is processed by a computing machine for edge detection, for example in order to determine the location of the object whose image was taken.
To reduce hardware costs and high computational requirements of processing large images, the images are often under-sampled and parts of the processing algorithm (such as edge detection) resort to sub-pixel measurements. Given a gray-value image (of an object) sampled onto a 2D discrete grid, it is possible to estimate the location of edges of the object with sub-pixel accuracy.
The sub-pixel edge detection relies on two properties common in natural images: (1) high spatial correlation that exists between neighboring pixels; and (2) intermediate gray-values which indicate sub-pixel edge position. Using these properties, several methods exist to detect edges of the image.
For example, the image is first enlarged and zoomed using interpolation. Interpolation, in this context, produces a larger image where the pixel values are mathematically estimated from values of neighboring pixels in the original image. Then, one or more edge detection kernels (also referred to as filters) are used to filter the zoomed image to enhance and detect, or locate, the edges. The filtering process is a convolution of two arrays of numbers (for example, the interpolated image and the filter kernel) to produce a third array of numbers.
Such edge detection filter might effectively take a second derivative of the interpolated image. The edge is located at the pixel interface in which the second derivative crosses the zero value. This technique is often called a zero-crossing technique. The zero-crossing technique and the filtering step are known in the art.
One drawback of the method is that it is computationally expensive and it requires increasing amount of computational power to increase accuracy. For example, to detect sub-pixel edges of an N×N image (for example a 100 by 100 2D grid image), the image is first enlarged by interpolation by a multiplication factor (for example two, four, or another integer). If the factor of four is used for interpolation, then the 100×100 image (having a total of 10,000 pixels) is interpolated into a 400×400 image (having a total of 160,000 pixels). Then, the filtering step (a computationally intensive step) is performed on the enlarged, interpolated image to find the edges of the image. To increase accuracy of the edge detection processes, either a larger original image is taken or the multiplication factor for the interpolation step is increased. Either way, the computational requirement of the filtering step is increased by the square of the increase of the interpolated image size.
There remains a need for a technique to increase edge detection accuracy without increasing the computational cost.